﻿/*
多数元素：
https ://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150、

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3, 2, 3]
输出：3

示例 2：
输入：nums = [2, 2, 1, 1, 1, 2, 2]
输出：2
*/
int majorityElement(int* nums, int numsSize)
{
    // 由于总是存在多数元素，因此我们不需要考虑没有多数元素的情况
    // 那我们可以直接将其进行排序。因为多数元素大于n/2个，
    // 因此排序之后的数组的中间的数一定是多数元素 【无论是n是奇数还是偶数】

    // 这里采用希尔排序 排升序
    int gap = numsSize;
    while (gap > 1) // >1是因为当gap = 2的时候进循环就会变成0 + 1就是1 也就是直接插入排序了。走完这趟肯定有序了
    {
        gap = gap / 3 + 1; // +1 是因为gap最后肯定是0。 +1之后就是直接插入排序

        for (int i = 0; i < numsSize - gap; i++) // 多组并排
        {
            int end = i;
            int tmp = nums[end + gap];
            while (end >= 0)
            {
                // 判断end是否大于 tmp
                if (nums[end] > tmp)
                {
                    nums[end + gap] = nums[end]; // 让前面的覆盖要交换的数字
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            // 退出while循环可能是break出来的，也可能是正常结束循环出来的
            // 如果是break出来的，这里就是直接让tmp 交换到之前的的位置
            // 如果是正常结束循环出来，那这里就是自己给自己赋值，不影响
            nums[end + gap] = tmp;
        }
    }

    // 走到这里排序完毕，返回中间的数
    return nums[numsSize / 2];

}